C++洛谷初赛题解

为了能顺利迎接CSP-JS的到来，又由于洛谷没有初赛题目的详细解析，所以“C++洛谷题解”专栏推出新的篇章——“C++洛谷初赛题解”！新的初赛题解与以往的题解格式有一定的差别，本人也是第一次做这种初赛的题解，所以初来乍到，请多指教。

好了，新的题解简介就介绍到这里。进入主题吧！

题目：

以下不属于面向对象程序设计语言的是（ ）。

A. C++

B. Python

C. Java

D. C

解析：

这道题个人认为应该不用多说了吧，C++、Python、Java都属于面向对象设计语言，只有C是面向过程设计语言。面向对象设计语言更倾向于想让计算机做什么，而面向过程设计语言更倾向于想让计算机怎么做。上一张图吧：

答案：

D

题目：

以下奖项与计算机领域最相关的是（ ）。

A. 奥斯卡奖

B. 图灵奖

C. 诺贝尔奖

D. 普利策奖

解析：

这道题也是送分题，但也详细的说一下吧：

看到这都明白了吧，正确答案就是图灵奖。再来扩展一下，中国只有清华姚班、智班创始人——姚期智，与2000年获得图灵奖。

答案：

B

题目：

目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。

A. 二进制

B. 十进制

C. 八进制

D. 十六进制

解析：

又来了一道送分题，还是详细的说一下吧：

这里说一下大型机：

具体更详细的可以自行百度，这里就不再叙述了。

答案：

A

题目：

以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为 （ ）。

A. N^{2}

B. N

C. N-1

D. N+1

解析：

从这道题开始就渐渐难起来了。但是有一点数学基础的人就知道，这种题就是概率问题。只要考虑最坏情况即可，最坏情况的次数就是N-1。

答案：

C

题目：

对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。

A. a, b, c, d, e

B. e, d, c, b, a

C. b, a, c, d, e

D. c, d, a, e, b

解析：

这道题还是比较简单的，只要学过栈就会做。我们一个个分析：

A：a入栈，a出栈，b入栈，b出栈，c入栈，c出栈，d入栈，d出栈，e入栈，e出栈。√

B：a入栈，b入栈，c入栈，d入栈，e入栈，e出栈，d出栈，c出栈，b出栈，a出栈。√

C：a入栈，b入栈，b出栈，a出栈，c入栈，c出栈，d入栈，d出栈，e入栈，e出栈。√

D：a入栈，b入栈，c入栈，c出栈，d入栈，d出栈，a出不了栈。⨉

栈作为线性数据结构中的线性表，最重要的特性是先进后出，或者说是后进先出，因此它又叫做先进后出表。栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为入栈，删除则称为出栈

答案：

D

题目：

对于有 n 个顶点、m 条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵树。

A. n-1

B. m-n

C. m-n-1

D. m-n+1

解析：

出题人开始疯狂出数据结构的题了。这道题其实背下来就行了，删掉 m-n+1 条边才能成为一棵树。先说一下无向连接图吧：

无向连接图是指对图中任意顶点u,v,都存在路径使u、v连通。反之则有有向连接图。一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD)为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。放两张图就清楚了：

无向连接图：

有向连接图：

 说白了，没箭头的图就是无向连接图，有箭头的就是有向连接图。

答案：

D

题目：

二进制数 101.11 对应的十进制数是（ ）。

A. 6.5

B. 5.5

C. 5.75

D. 5.25

解析：

这道题就看监考严不严了。如果严就不太好弄，如果不是很严就很好弄。先说不难的方法吧：

在线进制转换用这个网站一下就出来了，结果是5.75

如果严...

分解二进制数

(101)₂.(11)₂

计算整数部分

(101)₂ = 1*2² + 0*2¹ + 1*2⁰ = (5)₁₀

计算小数部分

(11)₂ = 1*2⁻¹ + 1*2⁻² = (75)₁₀

合并

(5)₁₀.(75)₁₀ = (5.75)₁₀ = 5.75

电脑打数学真不舒服

答案：

C

题目：

如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 （ ）种不同的形态？

A. 16

B. 15

C. 17

D. 32

解析：

又是一道数据结构的题，但这道题很简单。只需

2ⁿ⁻¹ = 2⁴ = 16

其中n就是层数

答案：

A

题目：

表达式 a*(b+c)*d 的后缀表达式为( )，其中“ * ”和“ + ”是运算符。

A. **a+bcd

B. abc+*d*

C. abc+d**

D. *a*+bcd

解析：

这道题需要搞清楚前缀表达式、中缀表达式、后缀表达式的相关知识。

中缀表达式

中缀表达式也就是我们平时数学里的运算，a*(b+c)*d就是一个中缀表达式。

3 + 4        5 - 6 * 7        (5 - 6) * 7        都是中缀表达式

前缀表达式

前缀表达式又称波兰表达式，大多数运算符都要放在左边。

+ 3 4        - 5 * 6 7        * - 5 6 7        都是前缀表达式

后缀表达式

后缀表达式又称逆波兰表达式，大多数运算符都放在右边

3 4 +        5 6 7 * -        5 6 - 7 *        都是后缀表达式

中缀表达式转前缀表达式

全体加括号

((a*(b+c))*d)

运算符放左括号外面

(*(a*+(b+c)d)

全体去括号(为了好看这里加了空格，实际上手写不用加)

* a * + b c d

中缀表达式转后缀表达式

全体加括号

((a*(b+c))*d)

运算符放右括号外面

((a(bc)+*)d)*

全体去括号

a b c + * d *

答案：

B

题目：

6 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有( )种。

A. 10

B. 15

C. 30

D. 20

解析：

这道题是一道纯纯的数学题，属于排列组合那里的知识(其实是考研的题)。这道题先放一边，先来说一下排列组合的相关知识：

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概念论关系密切。

排列的定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 或表示。计算公式：

组合的定义：从n个不同元素中，任取  个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 表示。

计算公式：，其中。

好了，排列组合的相关知识点就到这，现在看这道题，先列个式子：

C(6,2)×C(4,2)×C(2,2)÷A(3,3) =(6×5÷2)×(4×3÷2)×(2×1÷2)÷(3×2×1) =15×6×1÷6 =15

通过这个式子就可以得出最后的答案。这里还要说一下分组与分堆问题：

（1）均匀分组与不均匀分组

如果组与组之间的元素个数相同，则称为均匀分组；否则，称为不均匀分组。这道题是题目说道两人一队，所以是均匀分组。

（2）小组有名称或小组无名称

只是简单的分组，不考虑组别关系，则小组无名称；如果小组分为A组，B组，C组，种子队等，则小组有名称。如果均匀分组并且无名称，需要消序！消序即：除以堆数的全排列。而这道题题目说道不区分队伍的编号，即无名称小组。所以式子最后加上了A(3,3)用来消序。

答案：

B

题目：

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

A. 枚举

B. 贪心

C. 递归

D. 动态规划

解析：

这是一道最最经典的贪心问题，这道题应该不会有人答错。

答案：

B

题目：

由 1，1，2，2，3 这五个数字组成不同的三位数有（ ）种。

A. 18

B. 15

C. 12

D. 24

解析：

这道题是暴力枚举的题，但是可以直接算：3*2*1+4*3=18。没错，就是这么简单。

答案：

A

题目：

考虑如下递归算法：

则调用 solve(7) 得到的返回结果为（ ）。

A. 105

B. 840

C. 210

D. 420

解析：

这道题有两种解题方法，分别为作弊法和画图法。先说我最熟悉的作弊法：

所谓作弊法就是把代码抄下来，自行编译。这里已经写好了，复制去吧